1. Field of the Invention
This invention relates to the field of communication systems, and more particularly to a method and apparatus for scheduling upstream data packets in a broadband communication system.
2. Description of Related Art
Broadband communication systems facilitate high-speed connectivity and data transport from a point-to-multipoint basis. Exemplary broadband communication systems include cable modem systems that facilitate data transport between cable modems and information providers such as cable television networks and Internet web sites. FIG. 1 depicts a simplified block diagram of an exemplary cable modem system. As shown in FIG. 1, an exemplary cable modem system 10 comprises a wide area network (WAN) 12, a cable modem termination system (CMTS) 14, a plurality of cable modems (CM) 16 and a plurality of customer premises equipment (CPE) 18 (e.g., personal computers and televisions). The WAN 12 connects the cable modem system 10 to other networks such as a cable television network 22 or the well-known Internet via an Internet backbone 20. The CMTS 14 connects the plurality of cable modems 16 to the WAN 12. Cable modems typically provide high-speed Internet and cable television connectivity to businesses and homes.
Cable modem systems are described in more detail in a specification published by the Cable Television Laboratories, Inc., entitled “Data-Over-Cable Service Interface Specification Radio Frequency Interface Specification SP-RFIv1.1-I05-000714”, electronically available to the public at the URL of <http://www.cablemodem.com/specifications.html>, published in the year 2000, referred to hereinbelow as the “DOCSIS specification”, and hereby incorporated for reference herein in its entirety for its teachings on cable modem systems. As described in the DOCSIS specification, data packets transport data between cable modems and their associated CMTS. Upstream connectivity is defined herein as the transmission of data from the customer premises equipment. Downstream connectivity is defined herein as the transmission of data to the customer premises equipment (e.g., from a cable television network to the CPE). In cable modem systems, well-known protocols such as TDD and TDMA aid in scheduling data packet traffic on the upstream and downstream transmission paths.
Due to the wide variety of CPE service requirements, and due to the large number of CPEs serviced by any one CMTS, the bandwidth scheduling process in a broadband communication system such as that shown in FIG. 1 can become burdensome and complex. This is especially true with regard to the scheduling of upstream bandwidth. A CMTS typically schedules upstream bandwidth by assigning transmit opportunities on the upstream to its associated cable modems. A cable modem (CM) schedules upstream data from its associated CPEs by buffering the upstream data in an upstream input queue. The CM transmits upstream data from the upstream input queue to the CMTS during the CM's upstream transmit opportunities. Cable modems schedule upstream data within their input queues based on various factors such as message priority, message type and input order. Methods of scheduling upstream data help provide high-speed connectivity and data transport in broadband communication systems.
One method of scheduling upstream data utilizes well-known data transport techniques including burst information structures (BIS) and a linked list. The linked list comprises a plurality of BIS wherein a BIS is assigned a specific location within the linked list depending upon the “time to send” (TTS) of the BIS. The BIS are data structures containing information relating to the upstream data to be transported by a CM. In accordance with the now-described method of scheduling upstream data, a BIS comprises a TTS, a pointer to the upstream data and a next BIS (NB) pointer. The NB pointer points to the BIS located immediately after the current BIS on the linked list. The linked list is sorted in ascending order of TTS. Thus, the top or first BIS element of the linked list contains the next BIS to be transmitted. When software or firmware within the CM creates a new BIS, the software/firmware assigns the new BIS to its designated location within the linked list based upon the scheduled upstream transmission time of the BIS. Accordingly, the software/firmware rewrites NB pointers of adjacent BIS when a new BIS is inserted in the linked list. Thus, the NB pointer of the BIS immediately preceding the new BIS points to the new BIS. The NB pointer of the new BIS points to the BIS immediately after the new BIS. Disadvantageously, implementation of the above-described method for scheduling upstream data is relatively slow and complex. Due to software/firmware processing delays related to the linked list, the above-described method slows system performance. For example, upstream programming of the CM's microprocessor can cause as much as a 30 microsecond delay caused by response time to the well-known ARM microprocessor fast interrupt (FIQ). Also, processing delays of as much as 5 microseconds can occur when a new BIS is created because the software/firmware must sort the linked list. Another disadvantage of the above-described method is the added expense associated with programming and debugging the complex software/firmware source code needed to implement a linked list of BIS.
Therefore, a need exists for a method and apparatus for scheduling upstream data packets in a broadband communication system that is easily implemented, relatively fast and overcomes the disadvantages of prior art methods and apparatuses such as the above-described linked list of BIS method. The present invention provides such an upstream data packet scheduling method and apparatus.